package com.leetCode.problem;

import org.springframework.transaction.annotation.Transactional;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-22 14:12:14
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-22     张李鑫                     1.0         1.0 Version
 */
public class Problem44 {
    /**
     * 给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。
     */


    public static boolean isMatch(String s, String p) {
        char[] s1 = s.toCharArray();
        char[] p1 = p.toCharArray();
        return dp(s1, p1);

    }

    /**
     * process 版本会超时 但是思路是对的
     *
     * @param s1
     * @param p1
     * @param s
     * @param p
     * @return
     */
    private static boolean process(char[] s1, char[] p1, int s, int p) {
        // s走到边界了
        if (s == s1.length) {
            if (p == p1.length) {
                return true;
            } else {
                //*可以匹配任何字符 所以如果当前p是* 并且后续所有的都是* 代表匹配成功
                return p1[p] == '*' && process(s1, p1, s, p + 1);
            }
        }
        if (p == p1.length) {
            return false;
        }

        //上面已经探讨了边界值的状态 下面讨论正常的匹配状态
        //p当前字符串不是特殊字符的话 返回当前两个字符是不是相等
        //罗列所有是true 的可能 都没命中就返回false
        if (p1[p] != '*' && p1[p] != '?') {
            return p1[p] == s1[s] && process(s1, p1, s + 1, p + 1);
        }
        if (p1[p] == '?') {
            return process(s1, p1, s + 1, p + 1);
        }
        if (p1[p] == '*') {
            for (int length = 0; length <= s1.length - s; length++) {
                if (process(s1, p1, s + length, p + 1)) {
                    return true;
                }
            }
        }
        return false;
    }

    public static boolean dp(char[] s, char[] p) {
        int S = s.length;
        int P = p.length;
        boolean[][] dp = new boolean[S + 1][P + 1];
        dp[S][P] = true;
        for (int i = P - 1; i >= 0; i--) {
            dp[S][i] = p[i] == '*' && dp[S][i + 1];
        }

        for (int i = S - 1; i >= 0; i--) {
            for (int j = P - 1; j >= 0; j--) {
                if (p[j] != '*' && p[j] != '?') {
                    dp[i][j] = s[i] == p[j] && dp[i + 1][j + 1];
                } else if (p[j] == '?') {
                    dp[i][j] = dp[i + 1][j + 1];
                } else if (p[j]=='*'){
                    for (int length = 0; length <= S - i; length++) {
                        if (i + length <= S && dp[i + length][j + 1]) {
                            dp[i][j] = true;
                        }
                    }
                }
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        System.out.println(isMatch("aa", "*"));
    }
}
